Back to ARC Colloquium page

October 3, 2007
Láci Lovász
Eotvos Loránd University
Title: Which Graphs are Extremal?

Consider a problem in extremal graph theory of the following type: find the maximum density of a subgraph F in a graph, where the density of one
or more other subgraphs are fixed. More generally, we may want to maximize some linear combination of densities of various graphs. In almost all
cases when the answer is known, the extremal graph has a finite structure, at least asymptotically: the nodes can be partitioned into subsets with
given proportions, and the subgraphs between these classes are quasirandom with given densities. Is this always so?

To get a cleaner formulation of this, we formulate the question in terms of limits of growing graph sequences, which can be described by 2-variable
measurable symmetric functions from [0,1]^2 to [0,1]. The density of any finite simple graph in a such a function can be defined in a natural way.
Then the above problem leads to the following: which functions are "finitely forcible", i.e., uniquely determined by a finite number of subgraph densities?

With Vera Sos we proved that every stepfunction is finitely forcible. Somewhat surprisingly, the converse is not true, and one can find quite
general classes of finitely forcible functions (each of which describes the asymptotic structure of an extremal graph). We offer some necessary
and some sufficient conditions. A complete characterization seems difficult (but perhaps not hopeless).

This is joint work with Balazs Szegedy.